package 算法.线性表;

import java.util.Arrays;

/**
 * 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
 * <p>
 * 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
 * <p>
 * 第一个非叶子结点 arr.length/2-1
 */
public class 堆排序 {
    public static void main(String[] args) {
        Integer[] a = {5, 11, 8, 9, 1,5, 4, 3, 7, 6, 2, 0};
        for (int length = a.length-1; length >= 0; length--) {
            HeapSort(a,length);
            swap(a,0,length);
        }
        System.out.println(Arrays.toString(a));
    }

    private static void HeapSort(Integer[] a, int length) {
        // 构建大顶堆
        for (int i = length / 2 - 1; i >= 0; i--) {
            Heap(a, i, length);
        }
        System.out.println("当前堆的情况" + Arrays.toString(a));
    }


    private static void Heap(Integer[] a, int i, int length) {
        // 优化这段代码、减少交换次数
        for (int j = i; j <= length / 2 - 1; ) {
            int temp  = 2 * j + 1;  // 记录左、右节点中较大的一个
            if ((2 * j + 2 < a.length)&&(a[2 * j + 1]<a[2 * j + 2])) {  // 右叶子节点存在且右节点大于左节点
                temp = 2 * j + 2;
            }
            if (a[j]<a[temp]) //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                swap(a, j, temp);
            j = temp;
        }
        /*
        // 优化这段代码
        for (int j = i; j <= length / 2 - 1; ) {
            int temp = -1;
            if (2 * j + 2 < a.length) {  // 判断有叶子节点是否存在
                if (a[j] < a[2 * j + 2]) {
                    swap(a, j, 2 * j + 2);
                    temp = 2 * j + 2;
                }
            }
            if (a[j] < a[2 * j + 1])  // 左节点一定存在
            {
                swap(a, j, 2 * j + 1);
                temp = 2 * j + 1;
            }
            if (temp>0){
                j = temp;
            }else
                return;
        }
         */
    }

    private static void swap(Integer[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
